
''
''
'' This file is part of FreeBASIC Regular Expressions Library
''
''

Namespace FB
	
	Namespace RegExpLib
		
		
		#Include "dynarray.bi"
		
		'' constants
		
		Const CHAR_EOF			As String = !"\0"
		
		Const EPSILON			As Integer = -1
		
		Const ASSERT_BOF		As Integer = -2
		Const ASSERT_EOF		As Integer = -3
		
		'' ----------
		
		
		'' Boolean type		
		
		Enum Boolean
			False = 0
			True 	= Not False
		End Enum
		
		'' ----------
		
		
		'' Transition type
		
		Type StatePointer As State Pointer
		
		Type Transition
			char		As Integer
			target	As StatePointer
			Declare Constructor(c As Integer = EPSILON, t As StatePointer = 0)
		End Type
		
		Constructor Transition(c As Integer = EPSILON, t As StatePointer = 0)
			char = c
			target = t
		End Constructor
		
		DefineDynamicArrayType( Transition )
		
		'' ----------
		
		
		'' State type
		
		Type State
			accept		As Boolean = FALSE
			index			As Integer
			transition	As TransitionArray
			Declare Constructor(stateIndex As Integer = 0)
			Declare Sub Destroy
		End Type
		
		Constructor State(stateIndex As Integer = 0)
			index = stateIndex
		End Constructor
		
		
		Function ClearTransitions(ByRef Index As UInteger, ByRef Value As Transition, uParam As Any Pointer = 0) As Integer
			
			Value.target->Destroy
			
			Delete Value.target		
			
			Return 0
			
		End Function
		
		Sub State.Destroy
			
			' this Cast is needed cuz FBC (0.18.5) complains about "passing different pointer types"
			' but it's exactly the same pointer type passed which is expected... 
			' might be a FBC bug or it might be me cuz i'm coding this at 4:00 AM and i've run out of coffee... 
			transition.Iterate Cast(TransitionArrayIterator, ProcPtr(ClearTransitions))
			
		End Sub
		
		'' ----------
		
		
		
		#Include "preprocessor.bas"
		
		
		'' Compiler type (only one used outside RegExpLib namespace)
		
		Type Compiler
			
			Public:
			
				Pattern		As String
				IgnoreCase	As Boolean
				Multiline	As Boolean
				
				ErrorDescription	As String
				
				Declare Function Compile As Boolean
			
			#Ifndef FB_REGEXP_LIB_COMPILER_DEBUG
			
			Private:
			
			#EndIf
				
				iPos			As Integer
				sError		As String
				lookahead	As String * 1
				
				nextState	As Integer = 0
				
				Declare Function RegExp(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
				Declare Function Branch(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
				Declare Function Piece(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
				Declare Function Atom(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
				Declare Function Repeat(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
				Declare Function Literal(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
				
				Declare Sub NextChar
							
		End Type
		
		
		Function Inc(ByRef i As Integer) As Integer
			Function = i
			i += 1
		End Function
		
		
		Sub Compiler.NextChar
			
			Do
				iPos += 1
				
				If iPos > Len(Pattern) Then
					lookahead = CHAR_EOF
				Else
					lookahead = Mid(Pattern, iPos)
				EndIf
						
			Loop While InStr(lookahead, Any !"\&h20\&h09\&hA0") > 0
			
		End Sub
		
		Function Compiler.Compile As Boolean
			
			Dim As Preprocessor preproc 
			
			If preproc.Preprocess(Pattern, Multiline, IgnoreCase) Then
				
				iPos = 0			
				ErrorDescription = "No error"
				
				Dim As State Pointer	StartState, EndState
				
				nextState = 0
				
				NextChar
				
				If RegExp(StartState, EndState) Then
					
					EndState->accept = True
					
					Return True
					
				EndIf
				
			Else
				
				ErrorDescription = preproc.ErrorDescription
				
			EndIf
						
			Return False
			
		End Function
		
		'
		'  regexp ::= branch
      '           | branch "|" regexp
      '
		Function Compiler.RegExp(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
			
			Dim As State Pointer	A0, A1, B0, B1
						
			If Not Branch(A0, A1) Then Return False
				
			If lookahead = "|" Then
				
				NextChar
				
				If Not RegExp(B0, B1) Then Return False
					
				enter = New State(Inc(nextState))
				leave = New State(Inc(nextState))
				
				enter->transition.Add Type<Transition>(EPSILON, A0)
				enter->transition.Add Type<Transition>(EPSILON, B0)
				
				A1->transition.Add Type<Transition>(EPSILON, leave)
				B1->transition.Add Type<Transition>(EPSILON, leave)
				
			Else
				
				enter = A0
				leave = A1
				
			EndIf	
			
			Return True
			
		End Function
		
		'
		'  branch ::= piece
      '           | piece branch
      '
		Function Compiler.Branch(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
			
			Dim As State Pointer	A0, A1, B0, B1
						
			If Not Piece(A0, A1) Then Return False
				
			If InStr(lookahead, Any "|)" + CHAR_EOF) <= 0 Then
				
				If Not Branch(B0, B1) Then Return False
					
				enter = A0
				leave = B1
				
				A1->transition.Add Type<Transition>(EPSILON, B0)
				
			Else
				
				enter = A0	
				leave = A1
				
			EndIf
							
			Return True
			
		End Function
		
		
		'
		'  piece ::= atom
      '          | atom repeat
		'
		Function Compiler.Piece(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
			
			If Not Atom(enter, leave) Then Return False
				
			If InStr(lookahead, Any "*?") > 0 Then
				
				Return Repeat(enter, leave)
				
			EndIf
							
			Return True
				
		End Function
		
		
		'
		'  repeat ::= "*"
		'           | "?"
      '
		Function Compiler.Repeat(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
			
			Dim As State Pointer A0, A1, B0, B1
			
			A0 = New State(Inc(nextState))
			A1 = New State(Inc(nextState))

			A0->transition.Add Type<Transition>(EPSILON, enter)
			A0->transition.Add Type<Transition>(EPSILON, A1)			

			Select Case As Const Asc(lookahead)
				
				Case Asc("*"):		leave->transition.Add Type<Transition>(EPSILON, A0)
					
				Case Asc("?"):		leave->transition.Add Type<Transition>(EPSILON, A1)
										
			End Select

			enter = A0
			leave = A1
			
			NextChar
			
			Return True
			
		End Function
		
		
				
		'
		'  atom ::= "(" regexp ")"
      '         | assertion
      '         | literal
      '
		Function Compiler.Atom(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
			
			If lookahead = "(" Then
				
				NextChar
				
				If Not Regexp(enter, leave) Then Return False
				
				If lookahead <> ")" Then
					ErrorDescription = "Expected ) at offset " + Str(iPos)
					Return False
				EndIf
			
				NextChar
			
			ElseIf lookahead = "^" Then
				
				enter = New State(Inc(nextState))
				leave = New State(Inc(nextState))
				
				enter->transition.Add Type<Transition>(ASSERT_BOF, leave)
				
				NextChar
			
			ElseIf lookahead = "$" Then
				
				enter = New State(Inc(nextState))
				leave = New State(Inc(nextState))
				
				enter->transition.Add Type<Transition>(ASSERT_EOF, leave)
				
				NextChar
			
			Else
				
				Return Literal(enter, leave)
				
			EndIf			
			
			
			Return True
			
		End Function
		
		
		'
		'  literal ::= <ordinary character>
		'            | "\x" [1-9a-fA-F]{2}
		'            | "\" escape-char
		'
		'  escape-char ::= "\" | "(" | ")" | "|" | "*" | "?" | "^" | "$"
		'
		Function Compiler.Literal(ByRef enter As State Pointer, ByRef leave As State Pointer) As Boolean
			
			enter = New State(Inc(nextState))
			leave = New State(Inc(nextState))
				
			If lookahead = "\" Then
				
				NextChar
				
				If lookahead = "x" Then
					
					Dim As String hexnum
					
					NextChar
					
					If InStr(lookahead, Any "0123456789abcdefABCDEF") = 0 Then
						ErrorDescription = "Invalid escape sequence at offset " + Str(iPos)
						Return False
					EndIf
					
					hexnum = lookahead: NextChar
					
					If InStr(lookahead, Any "0123456789abcdefABCDEF") = 0 Then
						ErrorDescription = "Invalid escape sequence at offset " + Str(iPos)
						Return False
					EndIf
					
					hexnum += lookahead: NextChar
					
					enter->transition.Add Type<Transition>(ValInt("&H" & hexnum), leave)
					
				Else
					
					If InStr(lookahead, Any "\()|*?$^") = 0 Then
						ErrorDescription = "Invalid escape sequence at offset " + Str(iPos)
						Return False
					EndIf
					
					enter->transition.Add Type<Transition>(Asc(lookahead), leave)
					
					NextChar
					
				EndIf	
				
			ElseIf InStr(lookahead, Any "[](){}+*?") = 0 Then
				
				enter->transition.Add Type<Transition>(Asc(lookahead), leave)
					
				NextChar
				
			EndIf
			
			Return True
				
		End Function		
		
		'' ----------
		
	End Namespace
	
End Namespace
